package datastructure.tree;

import java.util.Stack;
import datastructure.linkedlist.Node;

/**
 *
 * @author Lei
 */
public class GetSortedLinkedListFromBST {

    // inoder travel for BST
    public static Node getSortedLinkedListFromBST(TreeNode bstNode) {
        Stack<TreeNode> nodes = new Stack<TreeNode>();
        Node head = new Node();

        while (!nodes.isEmpty() || null != bstNode) {
            if (null != bstNode) {
                nodes.push(bstNode);
                bstNode = bstNode.left;
            }
            else {
                bstNode = nodes.pop();
               
                Node old = head.next;
                Node newNode = new Node(bstNode.value);
                head.next = newNode;
                newNode.next = old;

                bstNode = bstNode.right;
            }
        }

        return head;
    }

    public static void main(String[] args) {

        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);

        n5.left = n2;
        n5.right = n6;
        n6.right = n7;

        n2.left = n1;
        n2.right = n4;

        Node p = GetSortedLinkedListFromBST.getSortedLinkedListFromBST(n5);
        while (p != null) {
            System.out.println(p.value);
            p = p.next;


        }


    }
}
